package com.zwj.interview.链表;

/**
 * 如何判断一个链表是不是回文？要求解法的时间复杂度是O（n），并且不得使用超过O（1）的辅助空间。
 * 如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。
 */
public class 判断链表是否是回文链表 {

    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        //下面就是找到中点，对于奇数链表，当fast.next==null，slow正好走到中点了
        //对于偶数链表的话，就是fast=null，slow落在中间两个节点的后一个节点上
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //我们的目的是要找到下半部分的起点，所以对于奇数链表，到中点时，slow还要往后再走一步
        //才会到达后半部分的起点
        if (fast != null) {
            slow = slow.next;
        }
        ListNode left = head;
        //走到这里，就拿到了下半部分链表的起点，翻转后半部分链表
        ListNode right = reverse(slow);
        //前半部分和后半部分进行对比，如果遇到不同的节点，则不是回文链表
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }
        //当然，我们这样是在原来链表上进行操作，改变了链表结构，我们还需要复原回去
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

}
